package developer.算法.堆.前K个高频元素;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author zhangyongkang
 * @time 2025/4/8 11:14
 * @description 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 */
public class KHigh {
    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        System.out.println(Arrays.toString(solution.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
//        //2,-1
        System.out.println(Arrays.toString(solution.topKFrequent(new int[]{4, 1, -1, 2, -1, 2, 3}, 2)));
        System.out.println(Arrays.toString(solution.topKFrequent(new int[]{1}, 1)));
    }


    static class Solution3 {
        Map<Integer, Integer> countMap;

        public int[] topKFrequent(int[] nums, int k) {
            //前K个高频元素 其实就是前K个元素的变种，构建大根堆的判断条件变了而已
            countMap = new HashMap<>();
            int[] res = new int[k];
            for (int num : nums) {
                Integer val = countMap.getOrDefault(num, 0) + 1;
                countMap.put(num, val);
            }
            //构建大根堆
            Set<Integer> integers = countMap.keySet();
            int[] countNms = new int[integers.size()];
            int idx = 0;
            for (Integer integer : integers) {
                countNms[idx++] = integer;
            }

            buildMaxHeap(countNms);

            int length = countNms.length;
            for (int i = 0; i < k; i++) {
                res[i] = countNms[0];
                int nexId = --length;
                //交换数组
                swap(countNms, 0, nexId);//第一个和
                heapModify(0, countNms, length);
            }
            return res;
        }

        private void buildMaxHeap(int[] nums) {
            int loop = (nums.length) / 2 - 1;//最后一个根节点的位置
            for (int i = loop; i > 0; i--) {
                heapModify(i, nums, nums.length);
            }
        }

        private void heapModify(int maxIdx, int[] nums, int limit) {
            int maxVal = countMap.getOrDefault(nums[maxIdx], 0);
            int maxIdxCurrent = maxIdx;

            int leftSonIdx = maxIdx * 2 + 1;
            int rightSonIdx = maxIdx * 2 + 2;

            if (leftSonIdx < limit && countMap.getOrDefault(nums[leftSonIdx], 0) > maxVal) {
                maxIdxCurrent = leftSonIdx;
            }

            if (rightSonIdx < limit && countMap.getOrDefault(nums[rightSonIdx], 0) > maxVal) {
                maxIdxCurrent = rightSonIdx;
            }
            if (maxIdxCurrent != maxIdx) {
                swap(nums, maxIdx, maxIdxCurrent);
                heapModify(maxIdxCurrent, nums, limit);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

    }

    static class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Long> numSizeMap = Arrays.stream(nums).boxed()
                    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
            List<Long> datas = new ArrayList<>(numSizeMap.values());
            //构建最大堆
            buildMaxHeap(datas);
            //选取前n个数字
            long[] valIdx = new long[nums.length + 1];
            int size = datas.size();
            for (int i = 0; i < k; i++) {
                Long l = datas.get(0);
                valIdx[Math.toIntExact(l)] = 1;
                //交换位置
                swap(datas, 0, datas.size() - 1 - i);
                heapModify(datas, 0, --size);
            }
            List<Integer> reuslt = new ArrayList<>();
            numSizeMap.forEach((a, b) -> {
                long valIdx1 = valIdx[Math.toIntExact(b)];
                if (valIdx1 == 1) {
                    reuslt.add(a);
                }

            });


            return reuslt.stream().mapToInt(Integer::intValue).toArray();

        }

        private void buildMaxHeap(List<Long> nums) {
            int size = nums.size();
            //最后一个非叶子结点的位置
            int loopSize = size / 2 - 1;
            for (int i = loopSize; i >= 0; i--) {
                heapModify(nums, i, size);
            }
        }

        private void heapModify(List<Long> nums, int maxIdx, int limit) {
            int largestIdx = maxIdx;
            int leftSon = largestIdx * 2 + 1;
            int rightSon = largestIdx * 2 + 2;

            //如果左侧儿子大  那么交换位置
            if (leftSon < limit && nums.get(leftSon) > (nums.get(largestIdx))) {
                largestIdx = leftSon;
            }

            if (rightSon < limit && nums.get(rightSon) > (nums.get(largestIdx))) {
                largestIdx = rightSon;
            }

            if (largestIdx != maxIdx) {
                swap(nums, largestIdx, maxIdx);
                heapModify(nums, largestIdx, limit);
            }
        }

        private void swap(List<Long> nums, int i, int j) {
            Long temp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, temp);
        }
    }
}
